\documentclass[12pt]{article}
\usepackage{calc,fancyhdr}
\usepackage[hmargin=.5in,vmargin=.75in,
            footskip=.25in,headsep=.5in-\headheight]{geometry}

% Template solution to Exercise 5.

% Common formatting macros for CSC165.
\usepackage{amsmath,amssymb}
\input{macros-165}

% Page layout: stretch text to fill up page.
\flushbottom

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{CSC\,165\,H1S}
\chead{Homework Exercise \#\,7}
\rhead{Winter 2014}

\begin{document}

\begin{large}
  \noindent
  Name: Robert Staskiewicz \hfill CDF login name: c3staski\\[0.5cm]
  Partner: Ekam Shahi    \hfill CDF login name: c3shahie
\end{large}

\medskip

\noindent
\rule{\textwidth}{.5pt}

\subsection*{Topic: Induction and Number Representation}

\medskip

\begin{enumerate}
 
       
    % place solution to question 1 below

    \item
    \medskip
    \noindent
    Consider the following sum:
    \begin{quote}
    $(\forall n \in \Z,\ n \geq1), \ 1+3+5+7+9+...+(2n-1)=n^2$
    \end{quote}
    {\bf Proof:} 
    \begin{pindent}
    	Let $P(n)$ be the statement that $(\forall n \in \Z,\ n \geq1), \ 1+3+5+7+9+...+(2n-1)=n^2$\\\\
		Base step: $P(1)$\\
		$2^1=1$\\
		$1=1$\\
		The formula holds for $P(1)$\\

        \begin{assumption}{$P(k)$ is true.}
		Then $1+3+5+7+9+...+(2k-1)=k^2 $\\
		Then $1+3+5+7+9+...+(2k-1)+(2(k+1)-1))=k^2+(2(k+1)-1) $\\
		Then $k^2+(2(k+1)-1))=k^2+(2k+2-1) $\\
		Then $k^2+(2(k+1)-1))=k^2+2k+1 $\\
		Then $k^2+2k+1 = (k+1)(k+1)$\\
		Then $(k+1)(k+1)=(k+1)^2 $\\
		Then $1+3+5+7+9+...+(2k-1)+(2(k+1)-1))=(k+1)^2 $\\
		Then $P(k+1)$ is True\\
		Therefore $P(k) \implies P(k+1)$\\
        \end{assumption}
        Therefore by the principle of mathematical induction:\\ $(\forall n \in \Z,\ n \geq1), \ \sum_{i=1}^{j} (2n-1)=n^2$.
        
        % $ \ \forall n \in \Z,\ \sum_{1}^{i} (2n-1) \equiv n^2  $
    \end{pindent}
    \medskip
    
    % place solution to question 2 below

    \item
    Consider the following claim:
    \begin{quote} 
        $$\forall n \in \N, n^3<4^n  $$
    \end{quote}
    {\bf Proof:}
    \begin{pindent}
    		Let $P(n)$ be the statement that $\forall n \in \N, n^3<4^n  $\\\\
    		Base step: $P(1)$\\
    		$1^3<4^1$\\
    		$1<4$\\
    		The formula holds for $P(1)$\\
            \begin{assumption}{$P(k)$ is true.}
            Then $k^3<4^k$\\
            Then $(k+1)^3<4^{k+1}$\\
			Then $4^{k+1}=(4)4^k>4k^3$\\
			Then $ 4k^3=k^3+k^3+k^3+k^3 $\\
			Then $ k^3+k^3+k^3+k^3>k^3 $\\
			Then $ k^3+k^3+k^3+k^3+3k^2+3k+1>k^3+3k^2+3k+1 $\\
			Then $ k^3+k^3+k^3+k^3+3k^2+3k+1>(k+1)^3 $ \just{Factoring.}\\
			Then $ (4)4^k>4k^3>(k+1)^3$\\
			Then $ 4(4)^k>(k+1)^3 $ \just{Transitive Property.}\\
			Then $ 4^{k+1}>(k+1)^3 $\\
			Then $ (k^3<4^k) \implies (4^{k+1}> 4^k) $\\
			
            \end{assumption}
            Therefore by the principle of mathematical induction,\ $\forall n \in \N, n^3<4^n  $
        \end{pindent}
        \medskip
       
    \item
    Consider the following problem:\\
    \begin{quote}
    Convert the Decimal number 3735928559 to Hexadecimal.
    \end{quote}

		{\bf Proof:} \\
		    \begin{pindent}
			
          \begin{assumption}{$3735928559$ is a Decimal number.}
                    		  		\begin{table}[h]
                    		  		\centering
                    		  		    \begin{tabular}{|l|l|l|}
                    		  		    \hline
                    		  		    Quotient   & Remainder & Hexadecimal \\ \hline
                    		  		    3735928559 & 15        & F           \\ \hline
                    		  		    233495534  & 14        & E           \\ \hline
                    		  		    14593470   & 14        & E           \\ \hline
                    		  		    912091     & 11        & B           \\ \hline
                    		  		    57005      & 13        & D           \\ \hline
                    		  		    3562       & 10        & A           \\ \hline
                    		  		    222        & 14        & E           \\ \hline
                    		  		    13         & 13        & D           \\ \hline
                    		  		    \end{tabular}
                    		  		\end{table}
          We need a sum:\\ $\exists x \in \N,\ x_1*16^7+x_2*16^6+x_3*16^5+x_4*16^4+x_5*16^3+x_6*16^2+x_7*16^1+x_8*16^0=3735928559$\\

		  Then $ 3735928559 \mod 16  =15$\\
		  Then $ 13*16^7=D=x_1$\\
		  Then $233495534 \mod 16 =14 $\\
		  		 Then $ 14*16^7=D=x_1$\\
		  Then $14593470 \mod 16 =14 $\\
		  		 Then $ 14*16^7=D=x_2$\\
		  Then $912091 \mod 16 = 11$\\
		  		 Then $ 11*16^7=D=x_3$\\
		  Then $57005 \mod 16 =13 $\\
		  		 Then $ 13*16^7=D=x_4$\\
		  Then $3562 \mod 16 =10 $\\
		  		 Then $ 10*16^7=D=x_5$\\
		  Then $222 \mod 16 =14 $\\
		  		 Then $ 14*16^7=D=x_6$\\
		  Then $222 \mod 16 =13 $\\
		  		 Then $ 13*16^7=D=x_7$\\

          \end{assumption}
          Then 
          $3735928559=13*16^7+14*16^6+10*16^5+13*16^4+11*16^3+14*16^2+14*16^1+15*16^0 $\\
          Therefore, 13,14,10,13,11,14,14,15  = DEADBEEF
          
      \end{pindent}
      
      \medskip
      
       \item
       Consider the following claim:\\
       \begin{quote}
		let $x \in \N$. Prove that if the sum of the digits in x is divisible by 3 then x is also divisible by 3. 
       \end{quote}
       We can express this in the notation of symbolic logic as:
       $$\forall x \in \N, \ X= x_n+x_{n-1}+...+x_2+x_1+x_0, (3\mid (x_nx+x_{n-1}+...+x_2+x_1+x_0)) \implies (3\mid X)$$
       $$5 $$ \\
   		{\bf Proof:} \\
   		    \begin{pindent}
   		
             \begin{assumption}{$ 3\mid (x_nx+x_{n-1}+...+x_2+x_1+x_0)\\ X = x_nx_{n-1}...x_2x_1x_0$, where $x_0,x_1,...,x_n$ is $x_0*10^0,x_1*10^1,...,x_n*10^n $ \\ }
             We use congruence relation modulo: $(a\equiv b \mod c) \iff (c\mid (a-b))$\\
   			 Assume $10 \equiv 1 \mod 3 $  \just{10-9 is divisible by 3}\\
   			 Then $ 10^n \equiv 1 \mod 3 $ \just{$\forall n \in \N$}\\
   			 Then $ X= x_n*10^n+...+x_1*10^1+x_0*10^0 $ \just{Definition of a base 10 number system.}\\
   			    			  Then $ [10^n \equiv 1 \mod 3] \equiv [1^n \equiv 1 \mod 3] $\\
   			    			  Then $(3\mid (1^n-1)) \equiv (3\mid 0) \iff (10^n\equiv (1 \mod 3))$\\
   			 Then $ X \equiv x_n*1+...+x_1*1+x_0*1 $\\
   			 So $X \equiv (x_n+...+x_1+x_0) \mod 3 $\\
   			 Then $X$ is divisible by 3 iff the sum of its digits is divisible by 3   $X$ 
   			 
             \end{assumption}
             Therefore, $\forall x \in \N, \ X= x_n+x_{n-1}+...+x_2+x_1+x_0, (3\mid (x_nx+x_{n-1}+...+x_2+x_1+x_0)) \implies (3\mid X)  $
              
         \end{pindent}
         \medskip

\end{enumerate}

\noindent
\rule{\textwidth}{.5pt}

\end{document}
